package com.leetcode.search.backtracking;

import java.util.*;
import java.util.stream.Collectors;

/**
 * @author Dennis Li
 * @date 2020/7/26 21:50
 */
public class Permute_46 {

    List<List<Integer>> res = new ArrayList<>();

    public List<List<Integer>> permute(int[] nums) {
        if (nums == null || nums.length == 0)
            return res;
        backtrack(nums, new LinkedList<>());
        return res;
    }

    private void backtrack(int[] nums, LinkedList<Integer> track) {
        // 递归的退出条件
        if (track.size() == nums.length) {
            res.add(new LinkedList<>(track));
            return;
        }
        for (int num : nums) {
            // 避免重复选择的跳过条件
            if (track.contains(num))
                continue;
            // 添加元素
            track.add(num);
            // 开始向下决策
            backtrack(nums, track);
            // 取消选择 -- 添加到最后面，所以需要从最后面开始回溯
            track.removeLast();
        }
    }

    static class Solution {

        public static void main(String[] args) {
            int[] arr = {1, 2, 3};
            Solution solution = new Solution();
            List<List<Integer>> permute = solution.permute(arr);
            permute.forEach(System.out::println);
        }

        public List<List<Integer>> permute(int[] nums) {
            List<List<Integer>> res = new ArrayList<>();
            List<Integer> output = Arrays.stream(nums).boxed().collect(Collectors.toList());
            backtrack(output.size(), res, 0, output);
            return res;
        }

        private void backtrack(int n, List<List<Integer>> res, int first, List<Integer> output) {
            if (first == n) {
                res.add(new ArrayList<>(output));
            }
            for (int i = first; i < n; i++) {
                Collections.swap(output, first, i);
                // 下一层的决策是针对起点节点来说的
                backtrack(n, res, first + 1, output);
                Collections.swap(output, first, i);
            }
        }
    }

    static class Official {

        public static void main(String[] args) {
            int[] arr = {1, 2, 3};
            Official solution = new Official();
            List<List<Integer>> permute = solution.permute(arr);
            permute.forEach(System.out::println);
        }

        public List<List<Integer>> permute(int[] nums) {
            List<List<Integer>> res = new ArrayList<>();
            List<Integer> output = Arrays.stream(nums).boxed().collect(Collectors.toList());
            backtrack(output.size(), output, res, 0);
            return res;
        }

        public void backtrack(int n, List<Integer> output, List<List<Integer>> res, int first) {
            if (first == n) {
                res.add(new ArrayList<>(output));
            }
            for (int i = first; i < n; i++) {
                Collections.swap(output, first, i);
                backtrack(n, output, res, first + 1);
                Collections.swap(output, first, i);
            }
        }
    }

}
